/*
 *  SelectionOperator.cpp
 *  Genetski
 *
 *  Created by Srđan Rašić on 11/19/11.
 *
 */

#include "SelectionOperator.h"
#include <map>
#include <set>
#include <utility>
#include <cstdlib>
#include <algorithm>

class __Compare {
public:
	bool operator() (const std::pair<double, int> & a, const std::pair<double, int> & b) {
		return a.first < b.first;
	} 
};

struct __Comparison {
	__Comparison(Population& pop) : _pop(pop) {	}
	
	bool operator() (int i,int j) {
		return _pop.Fitness(i) < _pop.Fitness(j);
	}
private:
	Population& _pop;
};

std::vector<int> RouletteWheelSelectionOperator::Select(Population& pop, unsigned int numberOfIndividuals) {
	std::map<double, int> intervals;
	std::set<std::pair<double, int>, __Compare> fitnesses;
	
	double maxFitness = 0.0;
	
	for (unsigned int i = 0; i < pop.size(); i++) {
		fitnesses.insert(std::make_pair(pop.Fitness(i), i));
		
		if (pop.Fitness(i) > maxFitness)
			maxFitness = pop.Fitness(i);
	}
		
	
	std::set<std::pair<double, int>, __Compare>::iterator it = fitnesses.begin();
	
	intervals[0] = it->second;
	do {
		intervals[it->first] = it->second;
	} while (++it != fitnesses.end());
	
	// select individuals
	std::vector<int> inds;
	std::map<double, int>::iterator iter;
	
	for (unsigned int i = 0; i < numberOfIndividuals; i++) {
		double r = maxFitness * (rand() / (double)RAND_MAX); // 0 ... maxFitness
		
		iter = intervals.lower_bound(r);
		int index = (iter++)->second;
	
//		if (std::find(inds.begin(), inds.end(), index) != inds.end())
//			i--;
//		else
			inds.push_back(index);
	}
	
	sort(inds.begin(), inds.end(), __Comparison(pop));
	
	return inds;
}


std::vector<int> KTournamentSelectionOperator::Select(Population& pop, unsigned int numberOfIndividuals) {
	std::vector<int> indices(numberOfIndividuals);
	
	for (unsigned int i = 0; i < numberOfIndividuals; i++) {
		indices[i] = (double)rand()/RAND_MAX*pop.size();
		
		// correct duplicates
		for (unsigned int j = 0; j < i; j++)
			if (indices[j] == indices[i]) {
				i--;
				break;
			}
	}
	
	sort(indices.begin(), indices.end(), __Comparison(pop));
	
	return indices;
}